package algorithms.leaning.class21;

import common.util.MyUtil;

/**
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 即便是值相同的货币也认为每一张都是不同的，
 * 返回组成aim的方法数
 * 例如：arr = {1,1,1}，aim = 2
 * 第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
 * 一共就3种方法，所以返回3
 *
 * @author guichang
 * @date 2021/6/22
 */

@SuppressWarnings("all")
public class Code2_动态规划_货币组成 {

    public static void main(String[] args) {
        int target = 3;
        int[] money = {1, 1, 1, 1, 1};
        MyUtil.print(ways(money, target));
        MyUtil.print(waysDp(money, target));
    }

    public static int ways(int[] money, int target) {
        if (money == null || money.length == 0 || target <= 0) {
            return 0;
        }
        return process(money, 0, target);
    }

    /**
     * 当前来到index位置，还剩rest需要组成
     */
    private static int process(int[] money, int index, int rest) {
        // 到最后了
        if (index == money.length) {
            return rest == 0 ? 1 : 0;
        }
        int ways = process(money, index + 1, rest);
        // 剪枝
        if (rest - money[index] >= 0) {
            ways += process(money, index + 1, rest - money[index]);
        }
        return ways;
    }

    public static int waysDp(int[] money, int target) {
        if (money == null || money.length == 0 || target <= 0) {
            return 0;
        }
        int N = money.length;
        int[][] dp = new int[N + 1][target + 1];
        dp[N][0] = 1;
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= target; rest++) {
                dp[index][rest] = dp[index + 1][rest];
                if (rest - money[index] >= 0) {
                    dp[index][rest] += dp[index + 1][rest - money[index]];
                }
            }
        }
        return dp[0][target];
    }

}